package com.xaicode.algorithm.leetcode._1_100;

import com.xaicode.utils.StdOut;

import java.util.Arrays;

/**
 * <a href="https://leetcode-cn.com/problems/longest-common-prefix">最长公共前缀</a>
 *
 * <p>编写一个函数来查找字符串数组中的最长公共前缀。</p>
 *
 * <p>如果不存在公共前缀，返回空字符串 <code>""</code>。</p>
 *
 * <p> </p>
 *
 * <p><strong>示例 1：</strong></p>
 *
 * <pre>
 * <strong>输入：</strong>strs = ["flower","flow","flight"]
 * <strong>输出：</strong>"fl"
 * </pre>
 *
 * <p><strong>示例 2：</strong></p>
 *
 * <pre>
 * <strong>输入：</strong>strs = ["dog","racecar","car"]
 * <strong>输出：</strong>""
 * <strong>解释：</strong>输入不存在公共前缀。</pre>
 *
 * <p> </p>
 *
 * <p><strong>提示：</strong></p>
 *
 * <ul>
 * 	<li><code>0 <= strs.length <= 200</code></li>
 * 	<li><code>0 <= strs[i].length <= 200</code></li>
 * 	<li><code>strs[i]</code> 仅由小写英文字母组成</li>
 * </ul>
 *
 * @author beborn xaicode@sina.com
 */
public class _14_Easy_LongestCommonPrefix {

    /*
        该题的前提是所有待匹配元素都以相同字符开始，限制了题目难度。
        通常情况下，该类题的描述可能为：计算随机数量的随机字符串的最长公共串。
     */

    public static void main(String[] args) {
        String[] params = new String[]{"flower", "flow", "flight"};
        StdOut.printfln("params is %s, expect result 'fl'.", Arrays.toString(params));

        _14_Easy_LongestCommonPrefix t = new _14_Easy_LongestCommonPrefix();
        String result;
        // horizontal
//        result = t.longestCommonPrefixHorizontal(params);
        // vertical
//        result = t.longestCommonPrefixVertical(params);
        // binary check
        result = t.longestCommonPrefixBinarySearch(params);
        // divide
//        result = t.longestCommonPrefixDivide(params);

        StdOut.printfln("result is %s.", result);
    }

    /**
     * 横向扫描
     * <p>
     * 以某一个元素为基准，依次与其他元素进行取最长公共前缀。
     * 通常情况下，公共前缀将在计算中逐渐变短。
     * 直到公共前缀长度为零时，即使并未全部计算，也可确定最长公共前缀为空。
     * <p>
     * 复杂度分析
     * <p>Time Complexity：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。
     * 最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
     * <p>Space Complexity：O(1)。使用的额外空间复杂度为常数。
     * <p>
     * 执行耗时:0 ms,击败了100.00% 的Java用户
     * 内存消耗:36.4 MB,击败了76.34% 的Java用户
     */
    public String longestCommonPrefixHorizontal(String[] params) {
        if (params == null || params.length == 0) {
            return "";
        }
        // specify arr[0] as benchmark
        String prefix = params[0];
        // max calculation count, may not reach to
        int count = params.length;
        // calculate from arr[1]
        for (int i = 1; i < count; i++) {
            // calculate arr[0] and arr[i]
            prefix = horizontalCheck(prefix, params[i]);
            // break if common prefix length is 0
            // as well as the longest-common-prefix of all elements in params array is empty string
            if (prefix.length() == 0) {
                break;
            }
        }
        return prefix;
    }

    private String horizontalCheck(String str1, String str2) {
        // get max calculation times
        int length = Math.min(str1.length(), str2.length());
        // record every calculation
        int index = 0;
        // check calculation times and
        // check whether the characters of the same subscript of two strings are the same
        while (index < length && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }
        //
        return str1.substring(0, index);
    }

    /**
     * 纵向扫描
     * <p>
     * 从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，
     * 如果相同则继续对下一列进行比较，
     * 如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。
     * <p>
     * 复杂度分析
     * <p>Time Complexity：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。
     * 最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
     * <p>Space Complexity：O(1)。使用的额外空间复杂度为常数。
     * <p>
     * 执行耗时:1 ms,击败了83.90% 的Java用户
     * 内存消耗:36.3 MB,击败了89.02% 的Java用户
     */
    public String longestCommonPrefixVertical(String[] params) {
        if (params == null || params.length == 0) {
            return "";
        }
        // LCP max length equal the shortest element in array
        // consider sort asc first, may cost more time or not
        int length = params[0].length();
        // max calculation time is N-1
        int count = params.length;
        for (int i = 0; i < length; i++) {
            // specify the ith character in arr[0]
            // and compare with character at the same position in arr[1..max]
            char c = params[0].charAt(i);
            for (int j = 1; j < count; j++) {
                // check compared character length first
                // if not equal, return sub(0..i)
                if (i == params[j].length() || params[j].charAt(i) != c) {
                    return params[0].substring(0, i);
                }
            }
        }
        // if run to this line, consider arr[0] is the shortest element in arr[0..max]
        return params[0];
    }

    /**
     * 二分查找
     * 最长公共前缀的长度不会超过字符串数组中的最短字符串的长度。
     * 用 minLength 表示字符串数组中的最短字符串的长度，则可以在 0~minLength 的范围内通过二分查找得到最长公共前缀的长度。
     * 每次取查找范围的中间值 mid，判断每个字符串的长度为 mid 的前缀是否相同，
     * 如果相同则最长公共前缀的长度一定大于或等于 mid，如果不相同则最长公共前缀的长度一定小于 mid。
     * 通过上述方式将查找范围缩小一半，直到得到最长公共前缀的长度。
     * <p>
     * 复杂度分析
     * <p>时间复杂度：O(mnlogm)，其中 m 是字符串数组中的字符串的最小长度，n 是字符串的数量。
     * 二分查找的迭代执行次数是 O(logm)，每次迭代最多需要比较 mn 个字符，因此总时间复杂度是 O(mnlogm)。
     * <p>空间复杂度：O(1)。使用的额外空间复杂度为常数。
     * <p>
     * 执行耗时:1 ms,击败了83.90% 的Java用户
     * 内存消耗:36.3 MB,击败了88.27% 的Java用户
     */
    public String longestCommonPrefixBinarySearch(String[] params) {
        if (params == null || params.length == 0) {
            return "";
        }
        // min length
        int minLength = Integer.MAX_VALUE;
        for (String str : params) {
            minLength = Math.min(minLength, str.length());
        }
        // limit binary search
        int low = 0, high = minLength;
        while (low < high) {
            // !! compute each binary search middle position
            int mid = (high - low + 1) / 2 + low;
            if (binaryCheck(params, mid)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return params[0].substring(0, low);
    }

    private boolean binaryCheck(String[] params, int length) {
        String first = params[0].substring(0, length);
        // length N-1
        int count = params.length;
        // compare arr[0]{0..mid} with each character of arr[1..max]{0..mid}
        for (int i = 1; i < count; i++) {
            String refer = params[i];
            for (int j = 0; j < length; j++) {
                // break if the same position character are not equal
                if (first.charAt(j) != refer.charAt(j)) {
                    return false;
                }
            }
        }
        // arr[0..mid] is or part of the longest common prefix, need further check
        return true;
    }

    /**
     * 分治
     * 拆分问题为子问题
     * <p>
     * 时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。
     * 时间复杂度 T(n)=O(mn)。
     * <p>
     * 空间复杂度：O(mlogn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。
     * 空间复杂度主要取决于递归调用的层数，层数最大为 logn，每层需要 m 的空间存储返回结果。
     * <p>
     * 执行耗时:0 ms,击败了100.00% 的Java用户
     * 内存消耗:36.6 MB,击败了37.01% 的Java用户
     */
    public String longestCommonPrefixDivide(String[] params) {
        if (params == null || params.length == 0) {
            return "";
        } else {
            return longestCommonPrefixDivide(params, 0, params.length - 1);
        }
    }

    private String longestCommonPrefixDivide(String[] params, int start, int end) {
        if (start == end) {
            return params[start];
        } else {
            // get middle position
            int mid = (end - start) / 2 + start;
            // LCP of arr[0..mid]
            String lcpLeft = longestCommonPrefixDivide(params, start, mid);
            // LCP of arr[mid+1..max]
            String lcpRight = longestCommonPrefixDivide(params, mid + 1, end);
            // LCP of [left, right]
            return commonPrefixDivide(lcpLeft, lcpRight);
        }
    }

    private String commonPrefixDivide(String lcpLeft, String lcpRight) {
        // get min length from two elements
        int minLength = Math.min(lcpLeft.length(), lcpRight.length());
        // compare and return the LCP from two elements
        for (int i = 0; i < minLength; i++) {
            if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {
                return lcpLeft.substring(0, i);
            }
        }
        return lcpLeft.substring(0, minLength);
    }

}
